Complexité de Rademacher Quantité définie par : $${\Bbb E}[\hat R_l(\mathcal G)]\quad\text{ avec }\quad\begin{align}\hat R_l(\mathcal G)&:={\Bbb E}\left[\sup_{g\in\mathcal G}\frac1l\sum^l_{i=1}\sigma_i g(Z_i)\,\middle|\,Z_1,\dots,Z_l\right]\\ &={\Bbb E}_\sigma\left[\sup_{g\in \mathcal G}\frac1l\sum^l_{i=1}\sigma_i g(Z_i)\right]\end{align}$$avec \(\sigma_1,\dots,\sigma_l\) des Variable aléatoire de Rademachers indépendantes de \((Z_1,\dots,Z_l)\) (⚠ les données sont fixées et l'espérance est calculée par rapport aux \((\sigma_i)_i\))

• on appelle \(\hat R_l(\mathcal G)\) la complexité empirique de Rademacher
    
• lemme de comparaison : si \(\psi\) \(:{\Bbb R}\to{\Bbb R}\) est \(L\)-lipschitzienne, alors en notant \(\mathcal G_\psi:=\{\psi\circ g\mid g\in\mathcal G\}\), on a \(\hat R_l(\mathcal G_\psi)\leqslant L\hat R_l(\mathcal G)\)
• cette notion est pratique puisqu'elle dépend des données, mais reste maniable sans se référer au pire des cas
• premiers résultats :
      
  1. Si \(\forall g\in \mathcal G\), \(0\leqslant g\leqslant1\), alors \(\forall t\geqslant0\), on a avec probabilité \(1-e^{-2t^2}\) que : $$\nu(g)\leqslant\hat\nu_l(g)+2R_l(\mathcal G)+\frac t{\sqrt l}$$